package com.majie.algorithm.practice;

import com.majie.algorithm.sort.QuickSort2;

/**
 * 找出数组中第N小的元素
 * 快速排序
 *
 * @author majie
 * @date 2018-05-07
 */
public class MinN {

    public static void main(String[] args) {
        int N = 6;
        int[] arr = {10, 66, 8, 3, 67, 5, 9, 4, 3, 1};  //1,3,3,4,5,8,9,10,66,67

        int result = sort(arr, 0, arr.length - 1, N);
        System.out.println(result);
    }

    private static int sort(int[] arr, int left, int right, int N) {
        //递归边界条件
        if (left == right) {
            return arr[left];
        }

        //求出零界点
        int partition = QuickSort2.partition(arr, left, right);

        //递归一边
        if (partition == N) {
            return arr[partition];
        } else if (partition < N) {
            return sort(arr, partition + 1, right, N);
        } else {
            return sort(arr, left, partition - 1, N);
        }

    }
}
